package Algorithms.recall;
/*
 * @Author 罗俊
 * @date 2020/10/29 - 7:41 下午
 *
 */

import java.util.LinkedList;
import java.util.List;
import java.util.concurrent.TimeUnit;

public class Recall2 {

    private static final int[][] HorseChessBroad = new int[10][10];

    private static boolean finished = false;

    public static void main(String[] args) {
        HorseChessLocation startLocation = new HorseChessLocation(4, 1);

        //HorseChessBroad[startLocation.getColumn()][startLocation.getRow()] = -1;
        long start = System.currentTimeMillis();
        go2(startLocation, 1);
        long end = System.currentTimeMillis();
        System.out.println("耗时："+(end-start));
    }

    /**
     * 贪心算法优化
     * 每次优先走下一步的可选下一步最多的步骤（提升了将近50%，远远不止）
     * @param availableNextStep
     */
    public static void greedy(List<HorseChessLocation> availableNextStep){
        availableNextStep.sort((c1,c2)->{

            List<HorseChessLocation> availableNextStep1 = availableNextStep(c1);
            List<HorseChessLocation> availableNextStep2 = availableNextStep(c2);
            return availableNextStep1.size()-availableNextStep2.size();
        });
    }

    public static void go2(HorseChessLocation horseChessLocation, Integer step) {

        if(finished){
            return;
        }

        HorseChessBroad[horseChessLocation.getColumn()][horseChessLocation.getRow()] = step;

        List<HorseChessLocation> availableNextStep = availableNextStep(horseChessLocation);

        greedy(availableNextStep);

        for (HorseChessLocation location : availableNextStep) {

            if (HorseChessBroad[location.getColumn()][location.getRow()] == 0) {
                // 还没有被访问过，走该点
                go2(location, step + 1);
            }
        }

        //System.out.println("===============");
        //System.out.println("第步走完是："+step);
        //printChessBroad();

        if (step < HorseChessBroad.length * HorseChessBroad[0].length) {
            // 还没有达到棋盘格子的数量，说明还没有走完，将整个棋盘清0
            HorseChessBroad[horseChessLocation.getColumn()][horseChessLocation.getRow()] = 0;

        } else {
            System.out.println("完成了");
            finished=true;
            printChessBroad();
        }
    }

    public static void printChessBroad() {
        for (int i = 0; i < HorseChessBroad.length; i++) {
            for (int j = 0; j < HorseChessBroad[i].length; j++) {
                System.out.print(HorseChessBroad[j][i] + "\t");
            }
            System.out.println();
        }
    }

    public static List<HorseChessLocation> availableNextStep(HorseChessLocation horseChessLocation) {

        List<HorseChessLocation> availableStep = new LinkedList<>();

        // 先右走两步
        int right2Step = horseChessLocation.getColumn() + 2;

        // 向右走一步
        int right1Step = horseChessLocation.getColumn() + 1;

        // 向上走一步
        int up1Step = horseChessLocation.getRow() - 1;

        // 向下走一步
        int down1Step = horseChessLocation.getRow() + 1;

        // 向上走两步
        int up2Step = horseChessLocation.getRow() - 2;

        // 向下走两步
        int down2Step = horseChessLocation.getRow() + 2;

        if (right2Step <= HorseChessBroad.length - 1) {
            // 可以向右踏（0、1、2、7）位置


            if (up1Step >= 0 && HorseChessBroad[right2Step][up1Step] == 0) {
                // 可以向上踏（0）


                availableStep.add(new HorseChessLocation(right2Step, up1Step));

            }


            if (down1Step <= HorseChessBroad[0].length - 1 && HorseChessBroad[right2Step][down1Step] == 0) {
                // 可以向下走

                availableStep.add(new HorseChessLocation(right2Step, down1Step));

            }
        }


        if (right1Step <= HorseChessBroad.length - 1) {


            if (up2Step >= 0 && HorseChessBroad[right1Step][up2Step] == 0) {

                availableStep.add(new HorseChessLocation(right1Step, up2Step));

            }


            if (down2Step <= HorseChessBroad[0].length - 1 && HorseChessBroad[right1Step][down2Step] == 0) {

                availableStep.add(new HorseChessLocation(right1Step, down2Step));
            }
        }

        // 先向左走两步
        int left2Step = horseChessLocation.getColumn() - 2;


        if (left2Step >= 0) {
            // 可以向右踏（0、1、2、7）位置

            if (up1Step >= 0 && HorseChessBroad[left2Step][up1Step] == 0) {
                // 可以向上踏（0）
                availableStep.add(new HorseChessLocation(left2Step, up1Step));
            }

            if (down1Step <= HorseChessBroad[0].length - 1 && HorseChessBroad[left2Step][down1Step] == 0) {
                // 可以向下走
                availableStep.add(new HorseChessLocation(left2Step, down1Step));
            }
        }

        // 向左走一步
        int left1Step = horseChessLocation.getColumn() - 1;
        if (left1Step >= 0) {


            if (up2Step >= 0 && HorseChessBroad[left1Step][up2Step] == 0) {
                availableStep.add(new HorseChessLocation(left1Step, up2Step));
            }

            if (down2Step <= HorseChessBroad[0].length - 1 && HorseChessBroad[left1Step][down2Step] == 0) {
                availableStep.add(new HorseChessLocation(left1Step, down2Step));
            }
        }

        return availableStep;
    }

}
